package com.重建二叉树;

import java.util.Arrays;

public class Solution {
    public TreeNode reConstructBinaryTree(int [] pre,int [] in) {
	if(pre!=null&&in!=null) {
		int root = pre[0];
		int i=0;
		TreeNode t = new TreeNode(root);//首先确定根节点
		t.left=t.right=null;
		for( i =0;i<in.length;i++) {/*
		在中序遍历中确定根节点的位置接着可以吧树
		分成左子树和右边子树两部分*/
			if(root == in[i]) {
				break;
			}
		}
		int leftnum=i;
		int rightnum=in.length-1-i;
		if(leftnum>0) {
			int[] leftin =new int[i];
			int[] leftpre = new int[i];
			System.out.println("此时的 i="+i);
			/*接下来的两部分主要是在根据根节点的位置
			 * 将左子树的前序和中序遍历复制的对应的数组
			 * 中去
			 * */
			System.arraycopy(in, 0, leftin, 0, i);
			System.arraycopy(pre, 1, leftpre, 0, i);
			t.left = reConstructBinaryTree(leftpre,leftin);
			
		}
		 if(rightnum>0) {
			int[] rightin = new int[in.length-1-i];
			int[] rightpre = new int[in.length-1-i];
			System.arraycopy(in, i+1, rightin, 0, in.length-1-i);
			System.arraycopy(pre, i+1, rightpre, 0, in.length-1-i);
			t.right=reConstructBinaryTree(rightpre,rightin);
			
		}
		
			return t;
	}	
	//代表如果是空的值那么就返回空值
	return null;
        
    }
}
